home *** CD-ROM | disk | FTP | other *** search
/ Aminet 5 / Aminet 5 - March 1995.iso / Aminet / dev / misc / LEDA_gene.lha / LEDA-3.1c-generic / prog / graph / dijkstra.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-08-05  |  3.0 KB  |  141 lines

  1. #define LEDA_CHECKING_OFF
  2.  
  3.  
  4. #include <LEDA/graph_alg.h>
  5. #include <LEDA/prio.h>
  6.  
  7.  
  8.  
  9.  
  10. void dijkstra(graph& G, 
  11.               node s, 
  12.               edge_array<int>&  cost, 
  13.               node_array<int>&  dist,
  14.               node_array<edge>& pred,
  15.               priority_queue<node,int>&   PQ)
  16. {
  17.   node_array<pq_item> I(G);
  18.   node v;
  19.                                                                                
  20.   forall_nodes(v,G)
  21.   { pred[v] = nil;
  22.     dist[v] = MAXINT;
  23.    }
  24.  
  25.   dist[s] = 0;
  26.   I[s] = PQ.insert(s,0);
  27.  
  28.   while (! PQ.empty())
  29.   { pq_item it = PQ.find_min();
  30.     node u = PQ.key(it);
  31.     int du = dist[u];
  32.     edge e;
  33.     forall_adj_edges(e,u)
  34.     { v = G.target(e);
  35.       int c = du + cost[e];
  36.       if (c < dist[v])
  37.       { if (dist[v] == MAXINT)
  38.           I[v] = PQ.insert(v,c);
  39.         else
  40.           PQ.decrease_inf(I[v],c);
  41.         dist[v] = c;
  42.         pred[v] = e;
  43.        }                                                                 
  44.      }
  45.     PQ.del_item(it);
  46.    }
  47. }
  48.  
  49.  
  50. #include <LEDA/impl/k_heap.h>
  51. #include <LEDA/impl/bin_heap.h>
  52. #include <LEDA/impl/m_heap.h>
  53. #include <LEDA/impl/p_heap.h>
  54. #include <LEDA/impl/list_pq.h>
  55.  
  56. #if !defined(__TEMPLATE_ARGS_AS_BASE__)
  57. declare3(_priority_queue,node,int,k_heap)
  58. declare3(_priority_queue,node,int,bin_heap)
  59. declare3(_priority_queue,node,int,m_heap)
  60. declare3(_priority_queue,node,int,p_heap)
  61. declare3(_priority_queue,node,int,list_pq)
  62. #endif
  63.  
  64.  
  65. main()
  66. {
  67.   GRAPH<int,int> G;
  68.  
  69.   for(;;)
  70.   {
  71.  
  72.   int n = read_int("# nodes = ");
  73.   int m = read_int("# edges = ");
  74.  
  75.   if (n==0) break;
  76.  
  77.   random_graph(G,n,m);
  78.  
  79.   edge_array<int>  cost(G);
  80.   node_array<int>  dist0(G);
  81.   node_array<int>  dist(G);
  82.   node_array<edge> pred(G);
  83.  
  84.   int M = read_int("max edge cost = ");
  85.  
  86.   node s = G.choose_node();
  87.  
  88.   edge e;
  89.   forall_edges(e,G) G[e] = cost[e] = random(0,M);
  90.  
  91.   priority_queue<node,int>* PQ[6];
  92.  
  93.   PQ[0] = new priority_queue<node,int>;
  94.  
  95. #if defined(__TEMPLATE_ARGS_AS_BASE__)
  96.   PQ[1] = new _priority_queue<node,int,k_heap>(n);
  97.   PQ[2] = new _priority_queue<node,int,m_heap>(M);
  98.   PQ[3] = new _priority_queue<node,int,list_pq>;
  99.   PQ[4] = new _priority_queue<node,int,p_heap>;
  100.   PQ[5] = new _priority_queue<node,int,bin_heap>(n);
  101. #else
  102.   PQ[1] = new _priority_queue(node,int,k_heap)(n);
  103.   PQ[2] = new _priority_queue(node,int,m_heap)(M);
  104.   PQ[3] = new _priority_queue(node,int,list_pq);
  105.   PQ[4] = new _priority_queue(node,int,p_heap);
  106.   PQ[5] = new _priority_queue(node,int,bin_heap)(n);
  107. #endif
  108.  
  109.   float T  = used_time();
  110.   cout << "DIJKSTRA: ";
  111.   cout.flush();
  112.   DIJKSTRA(G,s,cost,dist0,pred);
  113.   cout << string(" %6.2f sec\n",used_time(T));
  114.   newline;
  115.  
  116.   for(;;)
  117.   { int i = 
  118.     read_int("0:f_heap 1:k_heap 2:m_heap 3:list_pq 4:p_heap 5:bin_heap --> ");
  119.  
  120.     if (i>5) break;
  121.  
  122.     float T  = used_time();
  123.     dijkstra(G,s,cost,dist,pred,*(PQ[i]));
  124.  
  125.     cout << string("time: %6.2f sec\n",used_time(T));
  126.     newline;
  127.  
  128.     node v;
  129.     forall_nodes(v,G)
  130.        if( dist[v] != dist0[v]) 
  131.        { G.print_node(v);
  132.          cout << string("   dist =  %d   dist0 = %d\n",dist[v],dist0[v]);
  133.         }
  134.  
  135.    }
  136.  
  137.  }
  138.  
  139.  return 0;
  140. }
  141.